package Year22_Month06.day01;

import java.util.ArrayList;
import java.util.List;

public class 二叉树的层序遍历_DFS {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //首先排除root为null的情况
        if(root==null) {
            return new ArrayList<>();
        }
        List<List<Integer>> list  = new ArrayList<>();//创建一个list用来存储遍历的结果
        BFS(root,1,list);
        return list;
    }

    public void BFS(TreeNode node,int index,List<List<Integer>> list){
        //index用来控制层次，如果说当前到了一个新的层次，那么就要重新给list加一层,也就是加一个空数组
        if(list.size() < index){
            list.add(new ArrayList<>());
        }
        list.get(index - 1).add(node.val);
        //然后继续往下走
        if(node.left != null){
            BFS(node.left,index + 1,list);
        }
        if(node.right != null){
            BFS(node.right,index + 1,list);
        }

    }
}
